package cn.bellychang.wangzheng.graph.topological;

import java.util.LinkedList;

/**
 *
 * 有向无环图
 *
 * @author ChangLiang
 * @date 2021/2/20
 */
public class Graph {

    /**
     * 顶点的个数
     */
    private int v;

    /**
     * 邻接表
     */
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    /**
     * s 先于 t 边s->t
     * @param s
     * @param t
     */
    public void addEdge(int s, int t) {
        adj[s].add(t);
    }

    public void topoSortByKahn() {
        // 统计每个顶点的入度
        int[] inDegree = new int[v];

        // 通过一个双重for循环统计每个顶点的入度
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                // i->w
                int w = adj[i].get(j);
                inDegree[w]++;
            }
        }

        // 使用queue来暂存
        LinkedList<Integer> queue = new LinkedList<>();
        // 找到第一个入度为0的开始
        for (int i = 0; i < v; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int i = queue.remove();
            System.out.print("->" + i);
            for (int j = 0; j < adj[i].size(); j++) {
                int k = adj[i].get(j);
                // 把这个顶点可达的顶点的入度都减 1
                inDegree[k]--;
                if (inDegree[k] == 0) {
                    queue.add(k);
                }
            }
        }
    }

    public void topoSortByDFS() {

        // 先构建逆邻接表 边s->t表示 s依赖于t t先于s
        LinkedList<Integer>[] inverseAdj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            inverseAdj[i] = new LinkedList<>();
        }

        // 通过邻接表生成逆邻接表
        // 邻接表中，边 s->t 表示 s 先于 t 执行，也就是 t 要依赖 s。
        // 在逆邻接表中，边 s->t 表示 s 依赖于 t，s 后于 t 执行。
        // 为什么这么转化呢？这个跟我们这个算法的实现思想有关。
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                // i->w
                int w = adj[i].get(j);
                // w->i
                inverseAdj[w].add(i);
            }
        }

        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, inverseAdj, visited);
            }
        }
    }

    /**
     * 递归处理每个顶点。
     * 对于顶点 vertex 来说，我们先输出它可达的所有顶点，也就是说，先把它依赖的所有的顶点输出了，然后再输出自己。
     * @param vertex
     * @param inverseAdj
     * @param visited
     */
    private void dfs(int vertex, LinkedList<Integer>[] inverseAdj, boolean[] visited) {
        for (int i = 0; i < inverseAdj[vertex].size(); i++) {
            int w = inverseAdj[vertex].get(i);
            if (visited[w]) {
                continue;
            }
            visited[w]=true;
            dfs(w, inverseAdj, visited);
        }
        // 先把vertex这个顶点可达的所有顶点都打印出来之后 再打印它自己
        System.out.print("->" + vertex);
    }
}
